package com.example.lesson_10_25.JAVAHW.H1127;

/**
 * @PACKAGE_NAME: com.example.lesson_10_25.JAVAHW
 * @NAME: myAVL
 * @USER: jiang000
 * @DATE: 2023/11/27
 **/
import java.util.Comparator;
import java.util.Random;
import java.util.TreeSet;

class AVLNode<T> {
    T data;
    AVLNode<T> left, right;
    int height;

    public AVLNode(T data) {
        this.data = data;
        this.height = 1;
    }
}

class AVLTree<T> {
    private AVLNode<T> root;
    private Comparator<T> comparator;

    public AVLTree(Comparator<T> comparator) {
        this.comparator = comparator;
    }

    public void insert(T data) {
        root = insert(root, data);
    }

    public void delete(T data) {
        root = delete(root, data);
    }

    public boolean search(T data) {
        return search(root, data);
    }

    private int height(AVLNode<T> node) {
        return (node == null) ? 0 : node.height;
    }

    private int getBalance(AVLNode<T> node) {
        return (node == null) ? 0 : height(node.left) - height(node.right);
    }

    private AVLNode<T> insert(AVLNode<T> node, T data) {
        if (node == null)
            return new AVLNode<>(data);

        if (comparator.compare(data, node.data) < 0)
            node.left = insert(node.left, data);
        else if (comparator.compare(data, node.data) > 0)
            node.right = insert(node.right, data);
        else
            return node; // Duplicate data not allowed

        node.height = 1 + Math.max(height(node.left), height(node.right));

        int balance = getBalance(node);

        // Left Left Case
        if (balance > 1 && comparator.compare(data, node.left.data) < 0)
            return rightRotate(node);

        // Right Right Case
        if (balance < -1 && comparator.compare(data, node.right.data) > 0)
            return leftRotate(node);

        // Left Right Case
        if (balance > 1 && comparator.compare(data, node.left.data) > 0) {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }

        // Right Left Case
        if (balance < -1 && comparator.compare(data, node.right.data) < 0) {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }

        return node;
    }

    private AVLNode<T> delete(AVLNode<T> node, T data) {
        if (node == null)
            return node;

        if (comparator.compare(data, node.data) < 0)
            node.left = delete(node.left, data);
        else if (comparator.compare(data, node.data) > 0)
            node.right = delete(node.right, data);
        else {
            if ((node.left == null) || (node.right == null)) {
                AVLNode<T> temp = (node.left != null) ? node.left : node.right;
                if (temp == null) {
                    temp = node;
                    node = null;
                } else
                    node = temp;
            } else {
                AVLNode<T> temp = findMin(node.right);
                node.data = temp.data;
                node.right = delete(node.right, temp.data);
            }
        }

        if (node == null)
            return node;

        node.height = 1 + Math.max(height(node.left), height(node.right));

        int balance = getBalance(node);

        // Left Left Case
        if (balance > 1 && getBalance(node.left) >= 0)
            return rightRotate(node);

        // Left Right Case
        if (balance > 1 && getBalance(node.left) < 0) {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }

        // Right Right Case
        if (balance < -1 && getBalance(node.right) <= 0)
            return leftRotate(node);

        // Right Left Case
        if (balance < -1 && getBalance(node.right) > 0) {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }

        return node;
    }

    private boolean search(AVLNode<T> node, T data) {
        if (node == null)
            return false;

        int compareResult = comparator.compare(data, node.data);

        if (compareResult < 0)
            return search(node.left, data);
        else if (compareResult > 0)
            return search(node.right, data);
        else
            return true; // Found
    }

    private AVLNode<T> rightRotate(AVLNode<T> y) {
        AVLNode<T> x = y.left;
        AVLNode<T> T2 = x.right;

        x.right = y;
        y.left = T2;

        y.height = Math.max(height(y.left), height(y.right)) + 1;
        x.height = Math.max(height(x.left), height(x.right)) + 1;

        return x;
    }

    private AVLNode<T> leftRotate(AVLNode<T> x) {
        AVLNode<T> y = x.right;
        AVLNode<T> T2 = y.left;

        y.left = x;
        x.right = T2;

        x.height = Math.max(height(x.left), height(x.right)) + 1;
        y.height = Math.max(height(y.left), height(y.right)) + 1;

        return y;
    }

    private AVLNode<T> findMin(AVLNode<T> node) {
        while (node.left != null)
            node = node.left;
        return node;
    }
}


public class myAVL {
    private static int VALUE = 1000000;
    private static int PORTION = 500000;
    public static void testMyTree() {
        System.out.println("TEST MY MAP ");

        AVLTree<Integer> avlTree = new AVLTree<>(Integer::compareTo);
        // Insert 10000 random integers
        long startTime = System.currentTimeMillis();
        Random random = new Random();
        for (int i = 0; i < VALUE; i++) {
            avlTree.insert(random.nextInt(100000));
        }
        long endTime = System.currentTimeMillis();
        System.out.println("Insertion time: " + (endTime - startTime) + " ms");

        // Search for the inserted integers
        startTime = System.currentTimeMillis();
        for (int i = 0; i < VALUE; i++) {
            avlTree.search(random.nextInt(100000));
        }
        endTime = System.currentTimeMillis();
        System.out.println("Search time: " + (endTime - startTime) + " ms");
        startTime = System.currentTimeMillis();
        for (int i = 0; i < PORTION; i++) {
            avlTree.delete(random.nextInt(100000));
        }
        endTime = System.currentTimeMillis();
        System.out.println("Deletion time: " + (endTime - startTime) + " ms");
    }

    public static void testSystemTree() {
        System.out.println("TEST SYSTEM MAP ");


        // Insert 10000 random integers
        long startTime = System.currentTimeMillis();
        Random random = new Random();
        TreeSet<Integer> systemTree = new TreeSet<>();
        for (int i = 0; i < VALUE; i++) {
            systemTree.add(random.nextInt(100000));
        }
        long endTime = System.currentTimeMillis();
        System.out.println("Insertion time: " + (endTime - startTime) + " ms");

        // Search for the inserted integers
        startTime = System.currentTimeMillis();
        for (int i = 0; i < VALUE; i++) {
            systemTree.contains(random.nextInt(100000));
        }
        endTime = System.currentTimeMillis();
        System.out.println("Search time: " + (endTime - startTime) + " ms");
        startTime = System.currentTimeMillis();
        for (int i = 0; i < PORTION; i++) {
            systemTree.remove(random.nextInt(100000));
        }
        endTime = System.currentTimeMillis();
        System.out.println("Deletion time: " + (endTime - startTime) + " ms");
    }
    public static void main(String[] args) {
        System.out.println("添加元素总数为： " + VALUE);
        System.out.println("删除元素总数为： " + PORTION);
        testMyTree();
        testSystemTree();
    }
}
